package 递归or回溯;
import java.util.*;
/**
 * 计算数组中所有可能的组合，使其和等于目标值
 * 时间复杂度O(2^n)，空间复杂度O(n)，n为数组长度
 */
public class combinationSum {
    /**
     * 计算数组中所有可能的组合，使其和等于目标值
     * 
     * @param candidates 候选数组
     * @param target 目标值
     * @return 所有可能的组合列表
     */
    public static List<List<Integer>> combinationSumM(int[] candidates, int target){
        back(candidates, target, 0, 0); // 调用回溯方法计算组合
        return res; // 返回所有可能的组合列表
    }

    private static List<List<Integer>> res = new ArrayList<>(); // 用于存储所有可能的组合
    private static List<Integer> path = new ArrayList<>(); // 用于存储当前路径

    /**
     * 回溯方法，用于计算组合
     * 
     * @param candidates 候选数组
     * @param target 目标值
     * @param index 当前索引
     * @param sum 当前和
     */
    private static void back(int[] candidates, int target, int index, int sum){
        if(sum == target){ // 如果当前和等于目标值，表示找到一个有效组合
            res.add(new ArrayList<>(path)); // 将当前路径加入结果列表
            return; // 返回
        }
        if(index == candidates.length || sum > target) // 如果索引越界或当前和大于目标值，返回
            return;
        for(int i = 0; i < candidates.length; i++){ // 遍历候选数组
            sum += candidates[i]; // 更新当前和
            path.add(candidates[i]); // 将当前元素加入路径
            back(candidates, target, i, sum); // 递归计算组合
            sum -= candidates[i]; // 恢复当前和
            path.remove(path.size() - 1); // 移除当前元素
        }
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示候选数组
     * 例如：2,3,6,7 表示一个候选数组
     * 输出格式：所有可能的组合列表
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int target = sc.nextInt(); // 读取目标值
        int[] candidates = new int[s.length]; // 创建候选数组
        for(int i = 0; i < s.length; i++){ // 将输入转换为整数数组
            candidates[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        System.out.println(combinationSumM(candidates, target)); // 输出所有可能的组合
        sc.close(); // 关闭输入流
    }
}
